package com.atguigu.tree.threaded;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
//测试一把中序线索二叉树的功能
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");
//二叉树， 后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        //测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodesPre(root);
        //测试: 以 10 号节点测试
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10 号结点的前驱结点是 =" + leftNode); //3
        System.out.println("10 号结点的后继结点是=" + rightNode); //1
        //当线索化二叉树后， 能在使用原来的遍历方法
        //threadedBinaryTree.infixOrder();
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.threadedListMid(); // 8, 3, 10, 1, 14, 6
    }
}

class ThreadedBinaryTree {
    private HeroNode root;

    // 上一个节点, 用于辅助线索化
    private HeroNode pre;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder(){
        if (root!=null) {
            root.preOrder();
        }else{
            System.out.println("数据为空");
        }
    }

    public void midOrder(){

        if (root!=null) {
            root.midOrder();
        }else{
            System.out.println("数据为空");
        }
    }

    public void postOrder(){

        if (root!=null) {
            root.postOrder();
        }else{
            System.out.println("数据为空");
        }
    }

    public HeroNode preOrderFind(int id){
        if(root!=null){
            return root.preOrderFind(id);
        }else{
            return null;
        }
    }

    public HeroNode midOrderFind(int id){
        if(root!=null){
            return root.midOrderFind(id);
        }else{
            return null;
        }
    }

    public HeroNode postOrderFind(int id){
        if(root!=null){
            return root.postOrderFind(id);
        }else{
            return null;
        }
    }

    public boolean remove(int id){
        if(this.root!=null){
            if(this.root.getId()==id){
                this.root=null;
                return true;
            }else{
                return this.root.remove(id);
            }
        }else{
            return false;
        }
    }

    public void threadedNodesMid(){
        threadedNodesMid(root);
    }

    public void threadedNodesPre(HeroNode node){
        if (node==null) {
            return;
        }

        // todo 对当前节点进行线索化
        if(node.getLeft()==null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre!=null&&node.getRight()==null){
            node.setRight(pre.getRight());
            node.setRightType(1);
        }

        pre=node;

        // 先线索化左子树
        threadedNodesPre(node.getLeft());

        // 线索化右子树
        threadedNodesPre(node.getRight());
    }

    public void threadedNodesMid(HeroNode node){
        if (node==null) {
            return;
        }

        // 先线索化左子树
        threadedNodesMid(node.getLeft());

        // 对当前节点进行线索化
        if(node.getLeft()==null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre!=null&&pre.getRight()==null){
            pre.setRight(node);
            pre.setRightType(1);
        }

        pre=node;

        // 线索化右子树
        threadedNodesMid(node.getRight());
    }

    public void threadedListMid(){
        HeroNode node=root;
        while(node!=null){
            // 找到当前节点的最左节点 (中序遍历的最初节点)
            while(node.getLeftType()==0){
                node=node.getLeft();
            }
            System.out.println(node);

            // 逐次打印后继节点
            while(node.getRightType()==1){
                node=node.getRight();
                System.out.println(node);
            }


            // 对右节点遍历
            node=node.getRight();
        }
    }

    public void threadedListPre(){
        HeroNode node=root;
        while(node!=null){
            System.out.println(node);

            // 打印左部节点
            while(node.getLeft()!=null){
                node=node.getLeft();
                System.out.println(node);
            }

            // 打印右子树
            while(node.getRightType()==1){
                node=node.getRight();
                System.out.println(node);
            }

            node=node.getRight();
        }
    }

}


class HeroNode{
    private Integer id;
    private String name;

    private HeroNode left;
    private HeroNode right;

    // 类型.默认0,仅当1的时候表示前序或后继
    private int leftType;
    private int rightType;

    public HeroNode(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public void preOrder(){
        System.out.println(this);
        if (left!=null) {
            left.preOrder();
        }
        if (right!=null) {
            right.preOrder();
        }
    }

    public void midOrder(){

        if (left!=null) {
            left.midOrder();
        }
        System.out.println(this);
        if (right!=null) {
            right.midOrder();
        }
    }

    public void postOrder(){

        if (left!=null) {
            left.postOrder();
        }
        if (right!=null) {
            right.postOrder();
        }
        System.out.println(this);
    }

    public HeroNode preOrderFind(int id){
        System.out.println("id比较:"+this.id);
        if (this.id==id) {
            return this;
        }
        if (this.left!=null) {
            HeroNode heroNode = this.left.preOrderFind(id);
            if (heroNode!=null) {
                return heroNode;
            }
        }
        if(this.right!=null){
            HeroNode heroNode = this.right.preOrderFind(id);
            if (heroNode!=null) {
                return heroNode;
            }
        }
        return null;

    }

    public HeroNode midOrderFind(int id){

        if (this.left!=null) {
            HeroNode heroNode = this.left.midOrderFind(id);
            if (heroNode!=null) {
                return heroNode;
            }
        }
        System.out.println("id比较:"+this.id);
        if (this.id==id) {
            return this;
        }
        if(this.right!=null){
            HeroNode heroNode = this.right.midOrderFind(id);
            if (heroNode!=null) {
                return heroNode;
            }
        }
        return null;
    }

    public HeroNode postOrderFind(int id){

        if (this.left!=null) {
            HeroNode heroNode = this.left.postOrderFind(id);
            if (heroNode!=null) {
                return heroNode;
            }
        }
        if(this.right!=null){
            HeroNode heroNode = this.right.postOrderFind(id);
            if (heroNode!=null) {
                return heroNode;
            }
        }
        System.out.println("id比较:"+this.id);
        if (this.id==id) {
            return this;
        }

        return null;
    }

    public boolean remove(int id){
        System.out.println("id比较:"+this.id);
        if (this.left!=null) {
            if(this.left.id==id){
                this.left=null;
                return true;
            }
            boolean b = this.left.remove(id);
            if (b) {
                return b;
            }
        }
        if(this.right!=null){
            if (this.right.id==id) {
                this.right=null;
                return true;
            }
            boolean b = this.right.remove(id);
            if(b){
                return b;
            }
        }
        return false;

    }

}